package com.kjc.demo.basic.algorithmtest;

public class Test0929 {

	// 冒泡排序
	public void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; i < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}

	// 选择排序
	public void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int min = i;
			for (int j = i + 1; j < arr.length - 1; j++) {
				if (arr[min] > arr[j]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}

	// 插入排序
	public void insertSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] < arr[i - 1]) {
				int j = i;
				while (j > 0 && arr[j] < arr[j - 1]) {
					int temp = arr[j];
					arr[j] = arr[j - 1];
					arr[j - 1] = temp;
					j--;
				}
			}
		}
	}

	// 快速排序
	public void quickSort(int[] arr, int start, int end) {
		int i = start;
		int j = end;
		int pre = arr[start];
		while (i < j) {
			while (i < j && arr[j] > pre) {
				j--;
			}

			while (i < j && arr[i] < pre) {
				i++;
			}

			if (i < j && arr[i] == arr[j]) {
				i++;
			} else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		if (i - 1 > start) {
			quickSort(arr, start, i - 1);
		}
		if (i + 1 < end) {
			quickSort(arr, i + 1, end);
		}
	}

	// 希尔排序
	public void shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
			for (int i = gap; gap < arr.length; i++) {
				int j = i;
				while (j - gap > 0 && arr[j] < arr[j - gap]) {
					int temp = arr[j];
					arr[j] = arr[j - gap];
					arr[j - gap] = temp;
					j = j - gap;
				}
			}
		}
	}

	// 归并排序
	public void mergeSort(int[] arr, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			mergeSort(arr, left, mid);
			mergeSort(arr, mid + 1, right);
			merge(arr, left, mid, right);
		}
	}

	public void merge(int[] arr, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int i = left;
		int j = mid + 1;
		int k = 0;
		while (i < mid && j < right) {
			if (arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}

			while (i < mid) {
				temp[k++] = arr[i++];
			}

			while (j < right) {
				temp[k++] = arr[j++];
			}
			for (int k2 = 0; k2 < temp.length; k2++) {
				arr[left + k2] = temp[k2];
			}
		}
	}

	// 堆排序
	public void heapSort(int[] arr) {
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		for (int j = arr.length - 1; j > 0; j--) {
			int temp = arr[0];
			arr[0] = arr[j];
			arr[j] = temp;
			adjustHeap(arr, 0, j);
		}
	}

	public void adjustHeap(int[] arr, int i, int length) {
		int temp = arr[i];
		for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
			if (k + 1 < length && arr[k] < arr[k + 1]) {
				k++;
			}
			if (arr[k] > temp) {
				arr[i] = arr[k];
				i = k;
			} else {
				break;
			}
		}
		arr[i] = temp;
	}

	// 基数排序
	public static void radixSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		radixSort(arr, 0, arr.length - 1, maxbits(arr));
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

	// 计算最大位数
	public static int maxbits(int[] arr) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		int res = 0;
		while (max != 0) {
			res++;
			max /= 10;
		}
		return res;
	}

	// 基数排序
	// 数组，开始位置，结束位置，最大位数
	public static void radixSort(int[] arr, int begin, int end, int digit) {
		final int radix = 10;
		int i = 0, j = 0;
		int[] count = new int[radix];
		int[] bucket = new int[end - begin + 1];
		// 依次遍历每个位数
		for (int d = 1; d <= digit; d++) {
			for (i = 0; i < radix; i++) {
				count[i] = 0;
			}

			// 统计数量
			for (i = begin; i <= end; i++) {
				j = getDigit(arr[i], d);
				count[j]++;
			}

			// 计算位置
			for (i = 1; i < radix; i++) {
				count[i] = count[i] + count[i - 1];
			}

			// 记录到对应位置
			for (i = end; i >= begin; i--) {
				j = getDigit(arr[i], d);
				bucket[count[j] - 1] = arr[i];
				count[j]--;
			}
			for (i = begin, j = 0; i <= end; i++, j++) {
				arr[i] = bucket[j];
			}
		}
	}

	// 获取位数数值
	public static int getDigit(int x, int d) {
		return ((x / ((int) Math.pow(10, d - 1))) % 10);
	}

}
